/*
 * CommonNSubstring.cpp
 *	找出两个字符串里面，长度大于N的所有公共串。
 *	不包括长公共串中包括子公共串的情况。 如有一个公共串是： abcdefg  中包括 abc，.....
 *	这种情况下只计算abcdefg，不算它的子串
 *  Created on: 2012-5-17
 *      Author: xubin
 */

/*
 * 方法一： 先用求最长公共子串的办法DP扫描这两个串。（跟最长公共子序列不太一样）
 * 扫描完后，得到以 a[i],b[j]为结尾的串的最长公共子串的一个二维数组
 * 再扫描这个二维数组，找出公共子串长度大于N的公共子串。
 */
//TODO 这个方法感觉可以再优化，但是一下想不出来了

#define MAX(a,b) ((a)>(b)?(a):(b))
#define SAME(a,b) ((a)==(b)?1:0)
#define N 2

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int main() {
	string s1 = "aaaa";
	string s2 = "aaabaaaaaaaaa";
	vector<vector<int> > opt;
	unsigned i = 0;
	unsigned j = 0;

	for (i = 0; i < s1.length(); i++) {
		opt.push_back(vector<int>());
		for (j = 0; j < s2.length(); j++) {
			opt[i].push_back(int());
			if (i == 0 || j == 0) {
				opt[i][j] = SAME(s1[i], s2[j]);
			} else {
				opt[i][j] = opt[i - 1][j - 1] * SAME(s1[i], s2[j]) + SAME(s1[i], s2[j]) ; //如果s1i,s2j相同，则在前一位上加1，不同，则为0
//				opt[i][j] = opt[i - 1][j - 1] + SAME(s1[i], s2[j]);		//这是错的！！！
			}
		}
	}
	for (i = 0; i < s1.length(); i++) {
		for (j = 0; j < s2.length(); j++) {
			cout << opt[i][j] << ", ";
		}
		cout << endl;
	}
	cout << "---------------------------" << endl;

	//Starts From i=1 && j=1
	for (i = 1; i < s1.length(); i++) {
		for (j = 1; j < s2.length(); j++) {
			if (opt[i][j] > N) { //触发检查
				/*
				 * 检查大小的判断条件写得很复杂，有BUG
				 * 基本思想是在一个opt矩阵里面，i和j都是通过+1来向右方和下方来运动的：
				 *    ..... (i,j)   (i,j+1) ...
				 *    ......(i+1,j) (i+1,j+1)...
				 *    ......(i+2,j) (i+2,j+1)...
				 *    要找的就是向右，或者向下，或者向右下移动，且保证往这些方向移动时，公共串的长度是增加的。如果发现没有增加了，
				 *    就取这点的i,j值，往回计算公共的这个子串。
				 *    要注意的边界的情况，到了最下，或者最右方时，有一些条件就不用判断了。
				 *    根据i,j可以输出公共的串。这部分代码就不写了。
				 */
				if (i == s1.length() - 1 && j == s2.length() - 1) {
					if (1) { //最右下角的一个，不需要再判断输出
						cout << "i,j:" << i << ", " << j << endl;
					}
				} else if (i == s1.length() - 1) {
					if (opt[i][j] > opt[i][j+1]) {
						cout << "i,j:" << i << ", " << j << endl;
					}
				} else if (j == s2.length() - 1) {
					if (opt[i][j] > opt[i + 1][j]) {
						cout << "i,j:" << i << ", " << j << endl;
					}
				} else {		//比右边的元素大，比下面的元素也大，比右下的元素也大.如果是连续相等的值，一直到最下或者最右的一个值才会输出
					if (opt[i][j] > opt[i][j + 1] && opt[i][j] > opt[i + 1][j]
							&& opt[i][j] > opt[i + 1][j + 1]) {
						cout << "i,j:" << i << ", " << j << endl;
					}
				}
			}
		}
	}
}

